﻿using System.Runtime.InteropServices;
using System.Runtime.InteropServices.Marshalling;

namespace ZuoAlgorithms.Class006;

/// <summary>
/// 有序数组中是否存在一个数字
/// </summary>
public class Code01_FindNumber
{
    public void Main(int[] arr)
    {
        int N = 100;
        int V = 1000;
        int testTime = 500000;
        for (int i = 0; i < testTime; i++)
        {
            Random rand = new Random();
            int n = (int)(rand.Next() * N);
            int[] array = RandomArray(n, V);
            Array.Sort(array);
            int num = (int)(rand.Next() * V);
            if (Right(array, num) != Exist(array, num))
            {
                Console.WriteLine("出错了");
            }
        }
    }

    // 为了验证
    public int[] RandomArray(int n, int v)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            Random rand = new Random();
            arr[i] = (int)(rand.Next() * v) + 1;

        }
        return arr;
    }

    // 为了验证
    // 保证arr有序，才能用这个方法
    public bool Right(int[] sortedArr, int num)
    {
        foreach (var n in sortedArr)
        {
            if (n == num)
                return true;
        }
        return false;
    }

    // 保证arr有序，才能用这个方法
    public bool Exist(int[] arr, int num)
    {
        if (arr == null || arr.Length == 0)
            return false;
        int left = 0;
        int right = arr.Length - 1;
        int m = 0;
        while (left <= right)
        {
            m = (left + right) / 2;
            if (arr[m] == num)
            {
                return true;
            }
            else if (arr[m] > num)
            {
                right = m - 1;
            }
            else
            {
                left = m + 1;
            }
        }
        return false;
    }

}
